package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC815 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        public int size = 9;

        public int numBusesToDestination(int[][] routes, int S, int T) {
            if (S == T) return 0;

            this.size = routes.length;
            Set<Integer> sourceBusList = new HashSet<>();
            Set<Integer> targetBusList = new HashSet<>();
            Map<Integer, List<Integer>> stationAndBusMap = new HashMap<>();

            for (int i = 0; i < size; i++) {
                for (int station : routes[i]) {
                    if (stationAndBusMap.containsKey(station)) stationAndBusMap.get(station).add(i);
                    else {
                        List<Integer> busList = new ArrayList<>();
                        busList.add(i);
                        stationAndBusMap.put(station, busList);
                    }

                    if (station == S) sourceBusList.add(i);
                    if (station == T) targetBusList.add(i);
                }
            }

            int busGraph[][] = new int[size][size];
            for (List<Integer> stationForInterTransfer : stationAndBusMap.values()) {
                for (Integer busA : stationForInterTransfer) {
                    for (Integer busB : stationForInterTransfer) {
                        if (busA == busB) busGraph[busA][busB] = 0;
                        else busGraph[busA][busB] = 1;
                    }
                }
            }

            // start to travel min dist.
            int minBusDist = Integer.MAX_VALUE;
            for (Integer sourceBus : sourceBusList) {
                int[] dist = dijkstra(busGraph, sourceBus);
                for (int i = 0; i < dist.length; i++) {
                    if (targetBusList.contains(i)) minBusDist = Math.min(minBusDist, dist[i]);
                }
            }

            return minBusDist == Integer.MAX_VALUE ? -1 : minBusDist + 1;
        }


        public int[] dijkstra(int graph[][], int src) {
            int dist[] = new int[size];

            Boolean sptSet[] = new Boolean[size];

            for (int i = 0; i < size; i++) {
                dist[i] = Integer.MAX_VALUE;
                sptSet[i] = false;
            }

            dist[src] = 0;
            for (int count = 0; count < size - 1; count++) {
                int u = minDistance(dist, sptSet);
                sptSet[u] = true;
                for (int v = 0; v < size; v++) {
                    if (!sptSet[v] && graph[u][v] != 0 &&
                            dist[u] != Integer.MAX_VALUE &&
                            dist[u] + graph[u][v] < dist[v]) {
                        dist[v] = dist[u] + graph[u][v];
                    }
                }
            }

            return dist;
        }

        int minDistance(int dist[], Boolean sptSet[]) {
            //  初始化最小值
            int min = Integer.MAX_VALUE, min_index = -1;
            for (int v = 0; v < size; v++)
                if (sptSet[v] == false && dist[v] <= min) {
                    min = dist[v];
                    min_index = v;
                }
            return min_index;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[][] routes = InputUtil.toDoubleIntegerArray("[[1,7],[3,5]]");
        System.out.println(solution.numBusesToDestination(routes, 5, 5));
    }

    public static void main(String[] args) throws Exception {
        LC815 an = new LC815();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
